package leetcode.programmer;

// 面试题 08.11. 硬币（典型的完全背包）
public class WaysToChange {

    public static void main(String[] args) {

    }

    // 二维dp
    public int waysToChange1(int n) {
        //
        int[][] f = new int[5][n + 1];
        int[] coins = {1, 5, 10, 25};
        // 初始化，
        for (int i = 1; i < 5; i++) {
            f[i][0] = 1;
        }
        for (int i = 1; i < 5; i++) {
            for (int j = 1; j < n + 1; j++) {
                if (j < coins[i - 1]) {
                    // 当组成的钱小于当前硬币价值的时候，不选择
                    f[i][j] = f[i - 1][j] % 1000000007;
                } else {
                    f[i][j] = (f[i - 1][j] + f[i][j - coins[i - 1]]) % 1000000007;
                }
            }
        }
        return f[4][n];
    }


    // 一维dp,
    public int waysToChange2(int n) {
        int[] f = new int[n + 1];
        int[] coins = {1, 5, 10, 25};
        f[0] = 1; // 认为没有硬币也是一种情况
        for (int coin : coins) {
            for (int i = coin; i <= n; i++) {
                f[i] = (f[i] + f[i - coin]) % 1000000007;
            }
        }
        return f[n];
    }
}
